The computation of stationary distributions of Markov chains is an importanttask in the simulation of stochastic models. The linear systems arising in suchapplications involve non-symmetric M-matrices, making algebraic multigridmethods a natural choice for solving these systems. In this paper weinvestigate extensions and improvements of the bootstrap algebraic multigridframework for solving these systems. This is achieved by reworking thebootstrap setup process to use singular vectors instead of eigenvectors inconstructing interpolation and restriction. We formulate a result concerningthe convergence speed of GMRES for singular systems and experimentally justifywhy rapid convergence of the proposed method can be expected. We demonstrateits fast convergence and the favorable scaling behavior for various testproblems.
展开▼
